/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import static com.leetCode.Utils.printArray;

/**
 * @author : sunzb
 * @date: 2019/5/16
 */
public class _32_152_MaximumProductSubarray {

    int max = Integer.MIN_VALUE;

    public int maxProduct2(int[] nums) {
        int res = nums[0], max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int next_max = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));
            int next_min = Math.min(min * nums[i], Math.min(max * nums[i], nums[i]));
            min = next_min;
            max = next_max;
            res = Math.max(res, max);
        }
        return res;
    }

    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        int len = nums.length;
        int positive = 1;
        int negative = 1;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            if (num >= 0) {
                positive = Math.max(positive * num, num);
                negative = negative * num;
            } else {
                int negative1 = positive * num;
                positive = negative * num;
                negative = Math.min(negative1, num);
            }
            max = Math.max(max, positive);
        }
        return max;
    }

    public int maxProduct1(int[] nums) {
        if (nums.length == 0) return 0;
        printArray(nums);
        dfs(nums, 0, 1, 1);
        System.out.println("-----------------------------------");
        return max;
    }

    public void dfs(int[] nums, int i, int positive, int negative) {
        if (i == nums.length) return;
        int num = nums[i];
        if (num >= 0) {
            positive = positive * num;
            negative = negative * num;
            if (num > positive) positive = num;
            System.out.println(String.format("num:[%s],positive[%s],negative:[%s]", num, positive, negative));
        } else {
            int negative1 = positive * num;
            positive = negative * num;
            negative = negative1;
            if (num < negative) negative = num;
            System.out.println(String.format("num:[%s],positive[%s],negative:[%s]", num, positive, negative));
        }
        if (max < positive) max = positive;
        System.out.println("max:" + max);
        dfs(nums, i + 1, positive, negative);
    }

    public static void main(String[] args) {
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{2,3,-2,4}));
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{-2, 0, 1}));
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{0, 2}));
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{3, -1, 4}));
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{3, -1, -1, 4}));
        System.out.println(new _32_152_MaximumProductSubarray().maxProduct(new int[]{-2}));
    }
}
